/*
 * Copyright (c) Jack魏 2019 - 2022
 */

package com.jackwei.leetcode.t1dt10;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 作者：Jack魏
 * 题目连接： https://leetcode-cn.com/problems/two-sum/
 * 博客：https://blog.csdn.net/WeiHao0240/article/details/124520698
 *
 * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值target的那两个整数，并返回他们的数组下标。
 * 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
 *
 * 示例:
 * 给定 nums = [2, 7, 11, 15], target = 9
 * 因为 nums[0] + nums[1] = 2 + 7 = 9
 * 所以返回 [0, 1]
 */
public class L0001 {
    public static void main(String[] args) {
        int nums[] = new int[]{2, 7, 11, 15};
        int target = 9;
        System.out.println(Arrays.toString(new L0001().twoSum(nums, target)));
    }

    /**
     * 思路一：挨个遍历，先拿到数组的第一个数，然后依次加上后面的值进行比较target值，一旦匹配到就输出下标。
     * 本算法就是穷举法，将所有的可能进行计算。
     *
     * @param nums 数组
     * @param target 目标值
     * @return 数组两个值的下标
     */
    public int[] twoSum1(int[] nums, int target) {
        int numSize = nums.length;
        // 开始从第一个值开始找
        for (int i=0; i<numSize-1; i++){
            // 找过的值再往下找
            for (int j = i+1; j < numSize; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{};
    }

    /**
     * 思路二：可以想一想，我们如果知道一个值a，那另一个值就是target - a了，
     * 就是看这个值在不在数组里面，并返回这个值的下标，那么我们两个都知道了。
     *
     * @param nums 数组
     * @param target 目标值
     * @return 数组两个值的下标
     */
    public int[] twoSum(int[] nums, int target) {
        // 用来存放散列值，其中key为nums值，value为其下标。
        Map<Integer, Integer> map = new HashMap<>();
        for (int i=0; i<nums.length; i++){
            // 已知a
            int a = nums[i];
            // 根据target求出b
            int b = target - a;
            // 看看b是不是在数组里面（我们需要用散列值记录），如果在就返回。
            if (map.containsKey(b)){
                return new int[]{map.get(b), i};
            }
            // 如果不在散列值表里面，我们需要添加进去。
            map.put(a, i);
        }
        return new int[]{};
    }
}
